
#include "huf.h"
#include "my_types.h"

D_QUANT_OUT lpred;       
D_QUANT_OUT crpred;
D_QUANT_OUT cbpred;

struct huffentry {  //selfdefined type to store a combination of a value & a number of bits
  unsigned short val;
  unsigned short nb;
};

typedef struct huffentry HUF;

struct huffentry ldht[] = {  //DC light-value (Y) huffmantree
    {0x0, 2}, {0x2, 3}, {0x3, 3}, {0x4, 3}, {0x5, 3}, {0x6, 3},
    {0xe, 4}, {0x1e, 5}, {0x3e, 6}, {0x7e, 7}, {0xfe, 8}, {0x1fe, 9}};

struct huffentry cdht[] = {  //DC chrominance-value (Cb Cr) huffmantree
    {0x0, 2}, {0x1, 2}, {0x2, 2}, {0x6, 3}, {0xe, 4}, {0x1e, 5}, {0x3e, 6},
    {0x7e, 7}, {0xfe, 8}, {0x1fe, 9}, {0x3fe, 10}, {0x7fe, 11}};

struct huffentry laht[] = {  //AC light-value (Y) huffmantree
    {0x0a, 4}, {0x00, 2}, {0x01, 2}, {0x04, 3}, 
    {0x0b, 4}, {0x1a, 5}, {0x78, 7}, {0xf8, 8}, 
    {0x3f6, 10}, {0xff82, 16}, {0xff83, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x0c, 4}, {0x1b, 5}, {0x79, 7}, 
    {0x1f6, 9}, {0x7f6, 11}, {0xff84, 16}, {0xff85, 16}, 
    {0xff86, 16}, {0xff87, 16}, {0xff88, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1c, 5}, {0xf9, 8}, {0x3f7, 10}, 
    {0xff4, 12}, {0xff89, 16}, {0xff8a, 16}, {0xff8b, 16}, 
    {0xff8c, 16}, {0xff8d, 16}, {0xff8e, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x3a, 6}, {0x1f7, 9}, {0xff5, 12}, 
    {0xff8f, 16}, {0xff90, 16}, {0xff91, 16}, {0xff92, 16}, 
    {0xff93, 16}, {0xff94, 16}, {0xff95, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x3b, 6}, {0x3f8, 10}, {0xff96, 16}, 
    {0xff97, 16}, {0xff98, 16}, {0xff99, 16}, {0xff9a, 16}, 
    {0xff9b, 16}, {0xff9c, 16}, {0xff9d, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x7a, 7}, {0x7f7, 11}, {0xff9e, 16}, 
    {0xff9f, 16}, {0xffa0, 16}, {0xffa1, 16}, {0xffa2, 16}, 
    {0xffa3, 16}, {0xffa4, 16}, {0xffa5, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x7b, 7}, {0xff6, 12}, {0xffa6, 16}, 
    {0xffa7, 16}, {0xffa8, 16}, {0xffa9, 16}, {0xffaa, 16}, 
    {0xffab, 16}, {0xffac, 16}, {0xffad, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0xfa, 8}, {0xff7, 12}, {0xffae, 16}, 
    {0xffaf, 16}, {0xffb0, 16}, {0xffb1, 16}, {0xffb2, 16}, 
    {0xffb3, 16}, {0xffb4, 16}, {0xffb5, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1f8, 9}, {0x7fc0, 15}, {0xffb6, 16}, 
    {0xffb7, 16}, {0xffb8, 16}, {0xffb9, 16}, {0xffba, 16}, 
    {0xffbb, 16}, {0xffbc, 16}, {0xffbd, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1f9, 9}, {0xffbe, 16}, {0xffbf, 16}, 
    {0xffc0, 16}, {0xffc1, 16}, {0xffc2, 16}, {0xffc3, 16}, 
    {0xffc4, 16}, {0xffc5, 16}, {0xffc6, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1fa, 9}, {0xffc7, 16}, {0xffc8, 16}, 
    {0xffc9, 16}, {0xffca, 16}, {0xffcb, 16}, {0xffcc, 16}, 
    {0xffcd, 16}, {0xffce, 16}, {0xffcf, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x3f9, 10}, {0xffd0, 16}, {0xffd1, 16}, 
    {0xffd2, 16}, {0xffd3, 16}, {0xffd4, 16}, {0xffd5, 16}, 
    {0xffd6, 16}, {0xffd7, 16}, {0xffd8, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x3fa, 10}, {0xffd9, 16}, {0xffda, 16}, 
    {0xffdb, 16}, {0xffdc, 16}, {0xffdd, 16}, {0xffde, 16}, 
    {0xffdf, 16}, {0xffe0, 16}, {0xffe1, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x7f8, 11}, {0xffe2, 16}, {0xffe3, 16}, 
    {0xffe4, 16}, {0xffe5, 16}, {0xffe6, 16}, {0xffe7, 16}, 
    {0xffe8, 16}, {0xffe9, 16}, {0xffea, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0xffeb, 16}, {0xffec, 16}, {0xffed, 16}, 
    {0xffee, 16}, {0xffef, 16}, {0xfff0, 16}, {0xfff1, 16}, 
    {0xfff2, 16}, {0xfff3, 16}, {0xfff4, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x7f9, 11}, {0xfff5, 16}, {0xfff6, 16}, {0xfff7, 16}, 
    {0xfff8, 16}, {0xfff9, 16}, {0xfffa, 16}, {0xfffb, 16}, 
    {0xfffc, 16}, {0xfffd, 16}, {0xfffe, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0} };

struct huffentry caht[] = {  //AC chrominance-value (Cb Cr) huffmantree
    {0x00, 2}, {0x01, 2}, {0x04, 3}, {0x0a, 4}, 
    {0x18, 5}, {0x19, 5}, {0x38, 6}, {0x78, 7}, 
    {0x1f4, 9}, {0x3f6, 10}, {0xff4, 12}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x0b, 4}, {0x39, 6}, {0xf6, 8}, 
    {0x1f5, 9}, {0x7f6, 11}, {0xff5, 12}, {0xff88, 16}, 
    {0xff89, 16}, {0xff8a, 16}, {0xff8b, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1a, 5}, {0xf7, 8}, {0x3f7, 10}, 
    {0xff6, 12}, {0x7fc2, 15}, {0xff8c, 16}, {0xff8d, 16}, 
    {0xff8e, 16}, {0xff8f, 16}, {0xff90, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1b, 5}, {0xf8, 8}, {0x3f8, 10}, 
    {0xff7, 12}, {0xff91, 16}, {0xff92, 16}, {0xff93, 16}, 
    {0xff94, 16}, {0xff95, 16}, {0xff96, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x3a, 6}, {0x1f6, 9}, {0xff97, 16}, 
    {0xff98, 16}, {0xff99, 16}, {0xff9a, 16}, {0xff9b, 16}, 
    {0xff9c, 16}, {0xff9d, 16}, {0xff9e, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x3b, 6}, {0x3f9, 10}, {0xff9f, 16}, 
    {0xffa0, 16}, {0xffa1, 16}, {0xffa2, 16}, {0xffa3, 16}, 
    {0xffa4, 16}, {0xffa5, 16}, {0xffa6, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x79, 7}, {0x7f7, 11}, {0xffa7, 16}, 
    {0xffa8, 16}, {0xffa9, 16}, {0xffaa, 16}, {0xffab, 16}, 
    {0xffac, 16}, {0xffad, 16}, {0xffae, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x7a, 7}, {0x7f8, 11}, {0xffaf, 16}, 
    {0xffb0, 16}, {0xffb1, 16}, {0xffb2, 16}, {0xffb3, 16}, 
    {0xffb4, 16}, {0xffb5, 16}, {0xffb6, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0xf9, 8}, {0xffb7, 16}, {0xffb8, 16}, 
    {0xffb9, 16}, {0xffba, 16}, {0xffbb, 16}, {0xffbc, 16}, 
    {0xffbd, 16}, {0xffbe, 16}, {0xffbf, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1f7, 9}, {0xffc0, 16}, {0xffc1, 16}, 
    {0xffc2, 16}, {0xffc3, 16}, {0xffc4, 16}, {0xffc5, 16}, 
    {0xffc6, 16}, {0xffc7, 16}, {0xffc8, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1f8, 9}, {0xffc9, 16}, {0xffca, 16}, 
    {0xffcb, 16}, {0xffcc, 16}, {0xffcd, 16}, {0xffce, 16}, 
    {0xffcf, 16}, {0xffd0, 16}, {0xffd1, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1f9, 9}, {0xffd2, 16}, {0xffd3, 16}, 
    {0xffd4, 16}, {0xffd5, 16}, {0xffd6, 16}, {0xffd7, 16}, 
    {0xffd8, 16}, {0xffd9, 16}, {0xffda, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x1fa, 9}, {0xffdb, 16}, {0xffdc, 16}, 
    {0xffdd, 16}, {0xffde, 16}, {0xffdf, 16}, {0xffe0, 16}, 
    {0xffe1, 16}, {0xffe2, 16}, {0xffe3, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x7f9, 11}, {0xffe4, 16}, {0xffe5, 16}, 
    {0xffe6, 16}, {0xffe7, 16}, {0xffe8, 16}, {0xffe9, 16}, 
    {0xffea, 16}, {0xffeb, 16}, {0xffec, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x00, 0}, {0x3fe0, 14}, {0xffed, 16}, {0xffee, 16}, 
    {0xffef, 16}, {0xfff0, 16}, {0xfff1, 16}, {0xfff2, 16}, 
    {0xfff3, 16}, {0xfff4, 16}, {0xfff5, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0}, 
    {0x3fa, 10}, {0x7fc3, 15}, {0xfff6, 16}, {0xfff7, 16}, 
    {0xfff8, 16}, {0xfff9, 16}, {0xfffa, 16}, {0xfffb, 16}, 
    {0xfffc, 16}, {0xfffd, 16}, {0xfffe, 16}, {0x00, 0}, 
    {0x00, 0}, {0x00, 0}, {0x00, 0}, {0x00, 0} };

void huf_init() {  //initialising values
  lpred = 0;
  crpred = 0;
  cbpred = 0;
}
// D_QUANT_OUT  is a signed fixed integer of 8 bits
char magnitude(D_QUANT_OUT v) { //determines the number of bits of the given integer
  char mag = 0;
  if (v < 0)  //if it is a negative number, make it positive
    v = -v;
  while (v > 0) { //as long as the number is non-zero, shift it (divide by 2) and increase the local variable mag
    mag++;
    v >>= 1;
  }
  return mag;
}

void huf_run (fifo<D_QUANT_OUT>  *IN,   //B4 input buffer
          fifo<D_HUF_VAL>  *OUTVAL, //buffers to write the outputvalues to
          fifo<D_HUF_BITS>  *OUTBITS, //you add these as arguments so the method knows where to write to
          D_QUANT_OUT *pred, //previous DC value, necessary because these values are coded differentialy (different predecessor for Y and Cb Cr)
          HUF   *dcht,  //you add the huffman-tables as an argument, so you can reuse this code for luminance and luminance    DC table
          HUF   *acht) {  //AC table

  D_QUANT_OUT    diff;
  unsigned char len;
  D_QUANT_OUT    pix, level;
  int      run, cnt;
  HUF      e;
//first the DC value is coded
  if (IN->len() >= 64) { //only continue if you receive a block of at least 64 items
// in hardware, this is just the start-condition of the program... it means that the previous group has sent the complete block
    pix = IN->read(); //read the dc value

    diff  = pix - *pred; //calculate the difference with the previous block
    *pred = pix; //adjust the predecessor

    if (diff < 0){  //if the differencevalue is negative
      len = magnitude(-diff); //calculate the length
      e   = dcht[len]; //takes the len-th value out of the huffmantable
      OUTVAL->write(e.val); //write the value to the buffer
      OUTBITS->write(e.nb); //write the number of bits of the value to the buffer

// -1 in 2complement is 11111111110
// -1<<len is 111111111000000
// ~(-1<<len)   ==  00000000111111 (len times ending 1)
// diff.to_int() - 1 == differential value minus 1
// bitwise AND ==
// actually just conversion needed for negative numbers
      OUTVAL->write((diff.to_int()-1)&(~(-1<<len))); 
      OUTBITS->write(len);
    } else { //if the differencevalue is positive
      len = magnitude(diff);
      e = dcht[len];
      OUTVAL->write(e.val);  //write the values
      OUTBITS->write(e.nb);
      OUTVAL->write(diff);
      OUTBITS->write(len);
    }

    run = 0;
// next the AC value is coded
    for (cnt=1; cnt<64; ++cnt) { //do this 63 times
      pix   = IN->read(); //read the pixel
      level = pix; // copy the pixel to level
      if (level != 0) { //if level is not zero, continue
    if (level < 0) { //if level is negative
      len = magnitude(-level); //take the correct item out of the huffmantable
      while (run & ~0xf) { //check if run is bigger than 16   (bitwise AND with 0000, so if condition is still true, run is bigger than 16) do this untill you meet a non-zero value, write the zeros, then write the non-zero-values
        e = acht[0xf0]; //take the 240th (11110000) value out of the table, this is the last value, and is the special codeword for 16 consequtive zeros
        OUTVAL->write(e.val); //write this to the outputbuffers
        OUTBITS->write(e.nb);
        run -= 16; //lower run by 16, otherwise you will write the special codeword again
      }
      e = acht[(run<<4) | len]; //take the correct item out of the huffmantable for the non-zero bits (this is bitwise OR of len with run == xxxxx0000)
      OUTVAL->write(e.val); //write this value to outputbuffer
      OUTBITS->write(e.nb); //write nb bits to outputbuffer
      OUTVAL->write((level.to_int()-1)&(~(-1<<len))); //see above
      OUTBITS->write(len);
    } else { //if level is positive
      len = magnitude(level);
      while (run & ~0xf) { //write the special codeword for the 16 consequtive zeros
        e = acht[0xf0];
        OUTVAL->write(e.val);
        OUTBITS->write(e.nb);
        run -= 16;
      }
      e = acht[(run<<4) | len];
      OUTVAL->write(e.val);
      OUTBITS->write(e.nb);
      OUTVAL->write(level);
      OUTBITS->write(len);
    }
    run = 0;
      } else { //if level is zero, increase run (if you do this 16 times, you have enough zeros to add a special codeword)
    run++;
      }
    }
    //if you still have ending zeros, but not 16 or more, and you have no following non-zero bits, write the end-of-block codeword
    if (run > 0) {
      /* EOB */  // end of block
      e = acht[0];
      OUTVAL->write(e.val);
      OUTBITS->write(e.nb);
    }
  }

}
//runs the huf_run code for the correct input/output-buffers
void huf_l_run (fifo<D_QUANT_OUT> *IN, fifo<D_HUF_VAL> *OUTVAL, fifo<D_HUF_BITS> *OUTBITS) {
  huf_run(IN, OUTVAL, OUTBITS, &lpred, ldht, laht);
}

void huf_cr_run(fifo<D_QUANT_OUT> *IN, fifo<D_HUF_VAL> *OUTVAL, fifo<D_HUF_BITS> *OUTBITS) {
  huf_run(IN, OUTVAL, OUTBITS, &crpred, cdht, caht);
}

void huf_cb_run(fifo<D_QUANT_OUT> *IN, fifo<D_HUF_VAL> *OUTVAL, fifo<D_HUF_BITS> *OUTBITS) {
  huf_run(IN, OUTVAL, OUTBITS, &cbpred, cdht, caht);
}



